package william.stack;

import java.util.LinkedList;

/**
 * @author ZhangShenao
 * @date 2024/3/13
 * @description <a href="https://leetcode.cn/problems/valid-parentheses/">...</a>
 */
public class Leetcode20_有效的括号 {
    /**
     * 借助栈实现
     * 遍历字符串,针对每一个字符进行判断:
     * -如果是左括号,则将其入栈
     * -如果是有括号,则判断其与栈顶的左括号是否匹配
     * <p>
     * 时间复杂度O(N) 需要遍历一次字符串
     * 空间复杂度O(N) 额外申请了一个栈,长度为字符串长度
     */
    public boolean isValid(String s) {
        //边界条件校验
        if (s == null || s.isEmpty()) {
            return true;
        }

        //使用一个栈
        LinkedList<Character> stack = new LinkedList<>();

        //遍历字符串,针对每一个字符进行判断
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(' || c == '[' || c == '{') {  //遇到左括号,直接入栈
                stack.push(c);
                continue;
            }

            //遇到右括号,如果栈中没有匹配的左括号,则为非法括号
            if (stack.isEmpty()) {
                return false;
            }

            char left = stack.pop();
            char match;
            if (c == ')') {
                match = '(';
            } else if (c == ']') {
                match = '[';
            } else {
                match = '{';
            }

            if (left != match) {
                return false;
            }
        }

        //字符串遍历完成,判断栈是否为空
        return stack.isEmpty();
    }
}
